package number_336;

import java.util.*;

public class Solution {

    //timeout;
    public List<List<Integer>> palindromePairs1(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i != j) {
                    if (isPair(words[i] + words[j])) {
                        res.add(Arrays.asList(new Integer[]{i, j}));
                    }
                }
            }
        }
        return res;
    }

    private boolean isPair(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

    //哈希表;
    private List<String> wordRev = new ArrayList<>();
    private Map<String, Integer> indices = new HashMap<>();

    public List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        for (String word : words) {
            wordRev.add(new StringBuilder(word).reverse().toString());
        }
        for (int i = 0; i < n; i++) {
            indices.put(wordRev.get(i), i);
        }
        List<List<Integer>> ret = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String word = words[i];
            int m = word.length();
            if (m == 0) {
                continue;
            }
            for (int j = 0; j <= m; j++) {
                if (isPalindrome(word, j, m - 1)) {
                    int leftIndex = findWord(word, 0, j - 1);
                    if (leftIndex != -1 && leftIndex != i) {
                        ret.add(Arrays.asList(i, leftIndex));
                    }
                }
                if (j != 0 && isPalindrome(word, 0, j - 1)) {
                    int rightIndex = findWord(word, j, m - 1);
                    if (rightIndex != -1 && rightIndex != i) {
                        ret.add(Arrays.asList(rightIndex, i));
                    }
                }
            }
        }
        return ret;
    }

    private boolean isPalindrome(String word, int left, int right) {
        int center = right - left + 1;
        for (int i = 0; i < center / 2; i++) {
            if (word.charAt(left + i) != word.charAt(right - i)) {
                return false;
            }
        }
        return true;

    }

    private int findWord(String word, int left, int right) {
        return indices.getOrDefault(word.substring(left, right + 1), -1);
    }

    public static void main(String[] args) {
        new Solution().palindromePairs(new String[] {"bat","tab","cat"});
    }
}
